import java.util.HashMap;

public class Dichotomy {
    //牛客top101——二分查找/排序

    /**
     * 二分查找-Ⅰ
     * @param nums   int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left<=right){
            int mid = (right-left)/2+left;
            if (nums[mid]==target){
                return mid;
            } else if (nums[mid]<target) {
                left = mid+1;
            }else if (nums[mid]>target){
                right = mid-1;
            }
        }
        return -1;
    }

    /**
     * 二维数组中的查找
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
//        //暴力求解法
//        boolean f = false;
//        for (int i = 0; i < array.length; i++) {
//            for (int j = 0; j < array[0].length; j++) {
//                if (array[i][j] == target){
//                    f = true;
//                }
//            }
//        }
//        return f;

//        //哈希表法
//        HashMap<Integer,Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < array.length; i++) {
//            for (int j = 0; j < array[0].length; j++) {
//                hashMap.put(array[i][j],1);
//            }
//        }
//        if (hashMap.containsKey(target)){
//            return true;
//        }else {
//            return false;
//        }


        //分治
        //优先判断特殊
        if(array.length == 0)
            return false;
        int n = array.length;
        if(array[0].length == 0)
            return false;
        int m = array[0].length;
        //从最左下角的元素开始往左或往上
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){
            //元素较大，往上走
            if(array[i][j] > target)
                i--;
                //元素较小，往右走
            else if(array[i][j] < target)
                j++;
            else
                return true;
        }
        return false;
    }


    /**
     * 寻找峰值
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left<right){
            int mid = (right-left)/2+left;
            //右边是往下，不一定有坡峰
            if (nums[mid]>nums[mid+1]){
                right=mid;
            }else {
                //右边是往下，不一定有坡峰
                left=mid+1;
            }
        }
        return right;
    }


    /**
     * 数组中的逆序对
     * @param nums int整型一维数组
     * @return int整型
     */
    public int mod = 1000000007;
    public int mergeSort(int left, int right, int [] data, int [] temp){
        //停止划分
        if(left >= right)
            return 0;
        //取中间
        int mid = (left + right) / 2;
        //左右划分合并
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
        //防止溢出
        res %= mod;
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++)
            temp[k] = data[k];
        for(int k = left; k <= right; k++){
            if(i == mid + 1)
                data[k] = temp[j++];
            else if(j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
                //左边比右边大，答案增加
            else{
                data[k] = temp[j++];
                // 统计逆序对
                res += mid - i + 1;
            }
        }
        return res % mod;
    }
    public int InversePairs(int [] array) {
        int n = array.length;
        int[] res = new int[n];
        return mergeSort(0, n - 1, array, res);
    }


    /**
     * 旋转数组的最小数字
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]<min){
                min = nums[i];
            }
        }
        return min;
    }


    /**
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare (String version1, String version2) {
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0;
        int j = 0;
        while (i<n1||j<n2){
            long num1 = 0;
            while (i<n1&&version1.charAt(i)!='.'){
                num1 = num1*10+(version1.charAt(i)-'0');
                i++;
            }
            //遇到点跳过
            i++;
            long num2 = 0;
            while (j<n2 && version2.charAt(j)!='.'){
                num2 = num2*10 +(version2.charAt(j)-'0');
                j++;
            }
            j++;
            //比较谁大
            if (num1>num2){
                return 1;
            }
            if (num1<num2) {
                return -1;
            }
        }
        return 0;
    }
}
